package com.Algorithm.dac;

/**
 * @author shkstart
 * @create 2021-08-18 22:21
 */
public class HanoiTower {
    public static void main(String[] args) {
      hanoiTower(2,'A','B','C');
    }
    //汉诺塔问题，分治算法

    /**
     * 采用递归解决
     * @param num  盘子总数
     * @param a 起点位置
     * @param b 摆动需要的位置
     * @param c 终点的位置
     */
    public static  void hanoiTower(int num,char a,char b,char c){
        //如果只有一个盘中
        if (num==1){
            System.out.println("第1个盘子从"+a+"->"+c);
        }else {
            //如果有两个盘子以上
            //除了最下面的盘子以外，其余部分通过递归将从A柱子转移到B柱子
            hanoiTower(num-1,a,c,b);
            //将最后一个柱子从A转移到C柱子
            System.out.println("第"+num+"个盘子从"+a+"->"+c);
            //放在B的剩余部分从B转移到A
            hanoiTower(num-1,b,a,c);
        }
    }
}
